Análisis de algoritmos (página 2)

Partes: 1, 2

13
Notación asintótica
Objetivo: simplificar el análisis eliminando la información innecesaria (como "redondeo" 1,000,001~1,000,000)
Queremos decir de manera formal 3n2 ~ n2
Notación "O-grande (Big-Oh)":
dadas las funciones f(n) and g(n), decimos que f(n) es O(g(n) ) si y solo si hay constantes positivas c y n0 tal que f(n)= c g(n) para n = n0

14
Notación asintótica: ejemplo
Para funciones f(n) y g(n) (derecha) hay constantes positivas c y n0 tales que: f(n)=c g(n) for n = n0

conclusión:
2n+6 is O(n).

15
Notación asintótica: ejemplo
Otro caso.
n2 no es O(n) debido a que no hay c y n0 tal que:
n2 = cn para n = n0

(como se ve en el gráfico, no importa cuan grande se escoge c hay un n suficientemente grande que n2>cn ) .

16
Notación asintótica
Nota: Aun cuando es correcto decir que "7n – 3 es O(n3)", es mejor decir "7n – 3 es O(n)", esto es, se debe hacer la aproximación lo más cerca posible

Regla simple: Eliminar los términos de bajo orden y las constantes
7n-3 es O(n)
8n2log n + 5n2 + n es O(n2log n)

17
Notación asintótica (terminología)
Clases especiales de algoritmos:
logaritmico: O(log n)
lineal: O(n)
cuadratico: O(n2)
polinomico: O(nk), k = 1
exponencial: O(an), n > 1

"Alternativos" de Big-Oh
? (f(n)): Big Omega– cota inferior asintótica
? (f(n)): Big Theta– cota promedio asintótica

18
Tiempo de ejecución
Usar la notación Big-Oh para expresar el número de operaciones primitivas ejecutadas como función del tamaño de entrada.
Ejemplo: decimos que el algoritmo arrayMax se ejecuta en tiempo O(n).
Comparación de tiempos de ejecución asintóticos
– un algoritmo que corre en tiempo O(n) es mejor que uno que corre en tiempo O(n2)
– de forma similar, O(log n) es mejor que O(n)
– jerarquía de funciones: log n < < n < < n2 < < n3 < < 2n
Cuidado! Con los factores constantes muy grandes. Un algoritmo que corre en tiempo 1,000,000 n todavía es O(n) pero puede ser menor eficiente para un conjunto de datos que uno que corre en tiempo 2n2, que es O(n2)

19
Ejemplo de análisis asintótico
Algoritmo para calcular promedios prefijos:

Algorithm prefixAverages1(X):
Input: Array X de números de n-elementos.
Output: Array A de números de n -elementos tal que A[i] es el promedio de los elementos X[0], … , X[i].
Sea A un array de n números.
for i? 0 to n – 1 do
a ? 0
for j ? 0 to i do
a ? a + X[j]
A[i] ? a/(i+ 1)
return array A
Análisis: O(n2)

20
Ejemplo de análisis asintótico
Otro algoritmo para calcular promedios prefijos:
A[i-1] = (X[0] + X[1] +…+ X[i-1])/i
A[i] = (X[0] + X[1] +…+ X[i-1] + X[i])/(i+1)
Algorithm prefixAverages2(X):
Input: Array X de números de n-elementos.
Output: Array A de números de n -elementos tal que A[i] es el promedio de los elementos X[0], … , X[i].
Sea A un array de n números.
s? 0
for i ? 0 to n do
s ? s + X[i]
A[i] ? s/(i+ 1)
return array A
Análisis: O(n)

21
Complejidad en la práctica
Considerando 109 instrucciones/segundo

22
Análisis de algoritmos recursivos
Algorithm recursiveMax(A, n):
Input: Un array A que almacena n enteros.
Output: El máximo elemento en A.
if n = 1 then
return A[0]
return max {recursiveMax(A, n-1), A[n-1] }
Se usan ecuaciones de recurrencia

3 si n = 1
T(n) =
T(n-1) + 7 en otro caso

Forma cerrada: T(n) = 7(n-1) + 3

23
Elementos matemáticos
Sumatorios y series
Logaritmos y exponentes
propiedades de logaritmos:
logb(xy) = logbx + logby logb (x/y) = logbx – logby
logbxa = alogbx logba= logxa/logxb
propiedades de exponenciales:
a(b+c) = aba c abc = (ab)c
ab /ac = a(b-c) b = a logab
bc = a c*logab
Funciones especiales
Floor: ?x? = el mayor entero = x
Ceiling: ?x? = el menor entero = x

24
Elementos matemáticos
Técnicas de justificación (demostración)
Ejemplo y contraejemplo
Contrapositivo y Contradicción
Inducción
Invariantes de bucle
Probabilidades (algoritmos que usan random o análisis de rendimiento promedio de un algoritmo)

25
Otras técnicas
Amortización
Método contable
Funciones potenciales
Experimentación
Configuración
Selección de la cuestión
Decisión de lo que va a medir (Referencias a memoria, Comparaciones, Operaciones aritméticas)
Generación de los datos de prueba
Codificación de la solución y realización del experimento
Análisis de datos y visualización
La prueba del cociente
La prueba de potencia